LeetCode 206. Reverse Linked List (Easy)

題目連結

https://leetcode.com/problems/reverse-linked-list/

解題思路

• Linked list: 由節點(node)構成，一個用來儲存值，另一個是指針用來指向下一個節點。將多個 node 串連起來，形成 Linked list。
• ListNode 的結構:

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

• 範例說明:

const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

// 原始的 linked list：1 -> 2 -> 3 -> 4 -> 5

const reversedHead = reverseList(node1);

// 反轉後的 linked list：5 -> 4 -> 3 -> 2 -> 1

• 反轉節點: 原本的尾節點變成新的頭節點，而原本的頭節點變成新的尾節點

解法 1:迭代法

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  while (head) {
    let next = head.next;
    head.next = prev;
    prev = head;
    head = next;
  }
  return prev;
}

Complexity :

• Time: O(n)，n 是原本陣列的長度
• Space: O(1)

解釋:

1. prev 為 null，因為反轉後的新 Linked list 的尾節點的 next 應該是 null
2. 進入 while 迴圈，該迴圈將在 head 遍歷原始連結列表的節點時執行。當 head 為 null 時，表示已經處理完整個原始列表，迴圈結束。
3. 在每次迴圈迭代中，我們執行以下操作：

• 創建一個新變數 next 來存儲當前節點 head 的下一個節點引用。這是為了確保在修改 head 的 next 指針之後，我們仍然能夠訪問下一個節點。
• 將 head 的 next 指針設為 prev。這是實際的反轉步驟，將當前節點的 next 指向它的前一個節點 prev。
• 移動 prev 指向 head，這樣在下一次迭代中，prev 成為下一個節點的前一個節點。
• 移動 head 到下一個節點，即 next。這樣可以繼續處理下一個節點，直到整個列表都被反轉。

4. 當迴圈結束時，prev 指向反轉後的新連結列表的頭節點，因為在迴圈中，prev 一直在指向當前節點的前一個節點，而最後一次迭代時，prev 恰好指向新列表的頭節點。
5. 最後，返回 prev，這是新連結列表的頭節點，整個連結列表已經被反轉了。

解法 2:遞迴法

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Complexity :

• Time: O(n)，n 是 原本陣列的長度
• Space: O(n)

解釋:

1. 先检查如果 head 是 null 或只有一個節點，直接返回 head
2. 透過遞迴調用 reverseList(head.next) 來反轉 head 節點之後的部分，將结果存在 newHead 中
3. 將當前節點的下一個節點的 next 指針設置為當前節點，實現了反轉操作。
4. 將當前節點的 next 指針設置為 null，以防止循環。並返回新節點 newHead